For determining the distance between two points, a process may be employed to measure the coordinates (latitudes and longitudes) of the two points with a GPS (Global Positioning System) and to mathematically determine the distance between the two points from the measured coordinates. According to the GPS, radio waves transmitted from a plurality of satellites are received by a receiver, and the coordinates of the receiver are calculated based on the differences between the transmission and reception times of the radio waves.
A distance metric estimating system for estimating the distance metric between two nodes in a communication network according to similar principles is disclosed in Non-patent documents 1, 2. The distance metric refers to an index representative of the distance between the two nodes. In Non-patent documents 1, 2, a delay time is used as the distance metric.
As shown in FIG. 1, the distance metric estimating system disclosed in Non-patent documents 1, 2 includes coordinate calculating node 100, landmark nodes 110, 120, and coordinate-to-be-calculated nodes 130, 140. In FIG. 1, two landmark nodes and two coordinate-to-be-calculated nodes are shown for illustrative purposes. Actually, however, there are many landmark nodes and coordinate-to-be-calculated nodes involved, as shown in FIG. 2. In FIG. 2, the landmark nodes are represented by ●, coordinate calculating nodes by Δ, the coordinate-to-be-calculated nodes by ◯, and relay nodes by □.
Landmark nodes 110, 120 play the role of a GPS satellite, and have distance metric acquirers 111, 121, respectively. Each of distance metric acquirers 111, 121 has a function to measure the distance metric between its own node and the other landmark node and to send distance metric information which includes the measured distance metric and information indicating the nodes to which the measured distance metric refers (inter-node information), to coordinate calculating node 100.
Coordinate-to-be-calculated nodes 130, 140 include respective distance metric acquirers 131, 141, respective coordinate requesters 132, 142, respective coordinate storages 133, 143, and distance metric estimators 134, 144.
Distance metric acquirers 131, 141 have a function to measure distance metrics between their own nodes and landmark nodes 110, 120 and to send distance metric information which includes the measured distance metrics and information indicating nodes to which the measured distance metrics refer, to respective coordinate requesters 132, 142. Coordinate requesters 132, 142 have a function to send coordinate requests including the distance metric information sent from distance metric acquirers 131, 141, to coordinate calculating node 100, and store the coordinates of their own nodes which have been returned from coordinate calculating node 100 in response to the coordinate requests, in respective coordinate storages 133, 143. Distance metric estimators 134, 144 acquire coordinates from the coordinate storages of two coordinate-to-be-calculated nodes, and calculate an Euclidean distance therebetween thereby to estimate the distance metric between the two coordinate-to-be-calculated nodes.
Coordinate calculating node 100 includes coordinate axis generator 101, distance metric storage 102, coordinate axis storage 103, and coordinate calculator 104.
Distance metric storage 102 stores the distance metric information between landmark nodes which is sent from landmark nodes 110, 120. Coordinate axis generator 101 has a function to compress the distance metric information stored in distance metric storage 102 into a predetermined dimension number to generate a coordinate axis, and store the generated coordinate axis in coordinate axis storage 103. Coordinate calculator 104 calculates coordinates of coordinate-to-be-calculated nodes 130, 140 based on the distance metric information included in coordinate requests sent from coordinate-to-be-calculated nodes 130, 140 and the coordinate axis stored in coordinate axis storage 103, and return the calculated coordinates to the request sources.
The distance metric estimating system thus configured which is disclosed in Non-patent documents 1, 2 operates as follows:
First, distance metric acquirers 111, 121 of landmark nodes 110, 120 measure distance metrics between their own nodes and the other landmark nodes. Specifically, distance metric acquirers 111, 121 send messages to the other landmark nodes, measure RTTs (Round Trip Times) until they receive responses to the messages, and set the measured RTTs as distance metrics. Thereafter, distance metric acquirers 111, 121 send distance metric information which includes the measured distance metrics and inter-node information indicating nodes to which the measured distance metrics refer to, to coordinate calculating node 100. The distance metric information is stored in distance metric storage 102 of coordinate calculating node 100.
When the process of storing the distance metric information in distance metric storage 102 is completed, coordinate axis generator 101 generates a coordinate axis based on the distance metric information stored in distance metric storage 102.
The coordinate axis generating process will be described below with reference to a flowchart shown in FIG. 3. Coordinate axis generator 101 acquires the distance metric information between landmark nodes from distance metric storage 102 (step 2401). At this time, coordinate axis generator 101 acquires the RTTs between all landmark nodes. Thereafter, coordinate axis generator 101 performs a linear dimensional compression process to compress the acquired distance metric information into a predetermined dimension number to generate a coordinate axis, and stores the generated coordinate axis in coordinate axis storage 103 (step 2402).
Coordinate axis generator 101 performs the linear dimensional compression process according to a PCA (Principal Component Analysis). The PCA refers to a process of acquiring, from multidimensionally distributed data, one or more axes for increasing the dispersion of the data. For example, the PCA can calculates one or more axes by way of SDV (Singular Value Decomposition) expressed by the equation (1) below. The SDV as applied to the distance metric estimating system is directed to a matrix D having elements in rows and columns which are represented by the distance metrics between all landmark nodes. Of an obtained orthogonal matrix U, the same number of columns as the predetermined number represent a coordinate axis U′. In the equation (1), W represents a singular value matrix, V an orthogonal matrix, and VT a transposed matrix of V.D=U·W·VT  (1)
If coordinate-to-be-calculated nodes 130, 140 need the coordinates of their own nodes, then distance metric acquirers 131, 141 measure distance metrics between their own nodes and all other landmark nodes 110, 120. Specifically, distance metric acquirers 131, 141 execute Ping on all other landmark nodes, for example, and regard the obtained results as distance metrics. When the measurement of the distance metrics between their own nodes and all other landmark nodes 110, 120, has been performed distance metric acquirers 131, 141 send distance metric information which includes the measured distance metrics and information indicating nodes to which the measured distance metrics refer, to respective coordinate requesters 132, 142. Coordinate requesters 132, 142 then send coordinate requests including the distance metric information sent from distance metric acquirers 131, 141 to coordinate calculating node 100.
When the coordinate requests are sent from coordinate-to-be-calculated nodes 130, 140, coordinate calculating node 100 acquires the coordinate axis U′ from coordinate axis storage 103, and calculates the equation (2) shown below using the coordinate axis U′ and the distance metric information d1, d2 included in the coordinate requests sent from coordinate-to-be-calculated nodes 130, 140, thereby calculating coordinates c1, c2 of coordinate-to-be-calculated nodes 130, 140. Then, coordinate calculating node 100 returns the calculated coordinates c1, c2 to coordinate-to-be-calculated nodes 130, 140 as request sources.ci=U′Tdi   (2)
Coordinate requesters 132, 142 of respective coordinate-to-be-calculated nodes 130, 140 store the coordinates c1, c2 returned from coordinate calculating node 100 in respective coordinate storages 133, 143.
When distance metric estimator 134 of coordinate-to-be-calculated node 130 needs to estimate a distance metric between its own node and another coordinate-to-be-calculated node (which is assumed to be coordinate-to-be-calculated node 140), distance metric estimator 134 acquires the coordinates c1, c2 of coordinate-to-be-calculated nodes 130, 140 from coordinate storages 133, 143, and calculates the equation (3) shown below for determining a Euclidean distance between coordinate-to-be-calculated nodes 130, 140 thereby eliminating distance metric t12 between coordinate-to-be-calculated nodes 130, 140.t12=∥c1−c2∥  (3)